// addrspace.cc 
//	Routines to manage address spaces (executing user programs).
//
//	In order to run a user program, you must:
//
//	1. link with the -N -T 0 option 
//	2. run coff2noff to convert the object file to Nachos format
//		(Nachos object code format is essentially just a simpler
//		version of the UNIX executable object code format)
//	3. load the NOFF file into the Nachos file system
//		(if you haven't implemented the file system yet, you
//		don't need to do this last step)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"
#include "addrspace.h"
#include "noff.h"
#include "synch.h"
//----------------------------------------------------------------------
// 将全局变量初始化
// 用于分配空闲帧和pid号
// 初始化joinMutex 信号量
// 创建全局的标准输入输出文件
//----------------------------------------------------------------------
BitMap* AddrSpace::frameMap = new BitMap(NumPhysPages);

BitMap* AddrSpace::pidMap = new BitMap(PidNum); 
Semaphore** AddrSpace::joinMutex = new Semaphore*[PidNum + 10];
// 系统的全局页表
GlobalPageEntry* AddrSpace::globalPageTable = new GlobalPageEntry[NumPhysPages];
             //  下一个分配的用户进程号位
// 兑换区表，记录进程的页在兑换区的那个位置
BitMap* AddrSpace::swapMap = new BitMap(NumPhysPages);
SWAPEntry * AddrSpace::SwapTable = new SWAPEntry[NumPhysPages];
//----------------------------------------------------------------------
// SwapHeader
// 	Do little endian to big endian conversion on the bytes in the 
//	object file header, in case the file was generated on a little
//	endian machine, and we're now running on a big endian machine.
//----------------------------------------------------------------------

static void 
SwapHeader (NoffHeader *noffH)
{
	noffH->noffMagic = WordToHost(noffH->noffMagic);
	noffH->code.size = WordToHost(noffH->code.size);
	noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
	noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
	noffH->initData.size = WordToHost(noffH->initData.size);
	noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
	noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
	noffH->uninitData.size = WordToHost(noffH->uninitData.size);
	noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
	noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);
}

//----------------------------------------------------------------------
// AddrSpace::AddrSpace
// 	Create an address space to run a user program.
//	Load the program from a file "executable", and set everything
//	up so that we can start executing user instructions.
//
//	Assumes that the object code file is in NOFF format.
//
//	First, set up the translation from program memory to physical 
//	memory.  For now, this is really simple (1:1), since we are
//	only uniprogramming, and we have a single unsegmented page table
//
//	"executable" is the file containing the object code to load into memory
//----------------------------------------------------------------------

AddrSpace::AddrSpace(OpenFile *executable)
{
    NoffHeader noffH;
    unsigned int i, size;
    
    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
			+ UserStackSize;	// we need to increase the size
						// to leave room for the stack
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;

    // 再没有实现 SWIP 对换区之前，要求分配给新的用户进程的帧数，
    // 小于内存中剩余的帧数
    // 当实现SWIP 时，这里要修改
    //ASSERT(numPages <= frameMap->NumClear());		// check we're not trying
						// to run anything too big --
						// at least until we have
						// virtual memory
    ASSERT(pidMap->NumClear() > 0);



    // 分配进程号
    pid = pidMap->Find();
    // 数组中记录了子进程号 pid
    for(int i = 0;i < 100;i++)
        childPid[i] = -1;
    
     // 创建joinMutex 信号量
    ASSERT(joinMutex != NULL);
    joinMutex[pid] = new Semaphore("joinMutex",0);
    // 用户程序执行结束时，joinMutex[pid]-> P();

    // 初始化打开文件表
    // 0 标准输入 1 标准输出 2 错误输出

    OpenFile* stdIn = new OpenFile("stdIn");
    OpenFile* stdOut = new OpenFile("stdOut");
    OpenFile* stdErr = new OpenFile("stdErr");

    openFileTable[0] = stdIn;
    openFileTable[1] = stdOut;
    openFileTable[2] = stdErr;
    /*
    for(int i = 0;i < 3;i++)
        openFileTable[i] = nullptr; 
    */

    DEBUG('a', "Initializing address space, num pages %d, size %d\n", 
					numPages, size);
// first, set up the translation 

    // 创建一个新的页表
    // 需要再读一下MMU
    // MMU translate.cc 中translate函数
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
        //向内存中申请一个帧，将其装入内存中的对应物理帧
        int newPage = frameMap->Find();
        if(newPage == -1){
            printf("SWAP: do swap OUT\n");
            // 内存中没有空闲的页，将一个页随即替换掉。返回患处的页号
            newPage = swapOut();

        }
	    pageTable[i].virtualPage = i;	
	    pageTable[i].physicalPage = newPage;
	    pageTable[i].valid = TRUE;
	    pageTable[i].use = FALSE;
	    pageTable[i].dirty = FALSE;
	    pageTable[i].readOnly = FALSE;  // if the code segment was entirely on 
					// a separate page, we could set its 
					// pages to be read-only

        // 填入全局页表
        globalPageTable[newPage].virtualPage = i;	
        globalPageTable[newPage].physicalPage = newPage;
        globalPageTable[newPage].valid = TRUE;
        globalPageTable[newPage].use = FALSE;
        globalPageTable[newPage].dirty = FALSE;
        globalPageTable[newPage].readOnly = FALSE; 
        globalPageTable[newPage].pid = pid;
    }
    
// zero out the entire address space, to zero the unitialized data segment 
// and the stack segment
    // 在向内存中装入新程序之前，必要将内存清空，直接写覆盖
    //bzero(machine->mainMemory, size);

// then, copy in the code and data segments into memory
    // 将可执行文件中的内容写到处理机的主存中
    // 这里要按照线程的对应物理页号向主存写入
    // 因此，进行一个虚页号向实页号的转换
    // 注意，这不是段页式， 因此code 和data可能会在同一个页中
    if (noffH.code.size > 0) {
        DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
			noffH.code.virtualAddr, noffH.code.size);
        int counter = 0; // 用于计算该段已经向内存中读入了多少字节
        while(counter < noffH.code.size){
            // 接下来将向内存中写入最多一页的数据
            // virtualAddr 指明了接下来写入的第一个字节的地址，并由此来定位将写入的页 
            int virtualAddr = noffH.code.virtualAddr + counter;
            // 定位写入的起始位置
            int virtualPage = virtualAddr / PageSize;
            int offset = virtualAddr %  PageSize ; 
            int physicalPage = pageTable[virtualPage].physicalPage;
            // 向内存中写的目标位置
            int physicalAddr = physicalPage * PageSize + offset;
            // 确定要写入的长度
            // 当前页允许写入的长度 pageLast
            int pageLast = PageSize - offset;
            // noffH.code.size - counter 指明剩余的总长
            int size = ((noffH.code.size - counter) > pageLast) ? pageLast : (noffH.code.size - counter);
            DEBUG('a',"Writing code segment  into Mem , at virualAddr 0x%x, size %d physicalAddr 0x%x physicalPage %d offset %d\n", 
			virtualAddr, size, physicalAddr,physicalPage, offset);
            // 在可执行文件中的位置 noffH.code.inFileAddr + counter
            executable->ReadAt(&(machine->mainMemory[physicalAddr]),
			size, noffH.code.inFileAddr + counter);

            // 更新counter
            counter += size;
        }        
        
    }
    if (noffH.initData.size > 0) {
        DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", 
			noffH.initData.virtualAddr, noffH.initData.size);
        executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
			noffH.initData.size, noffH.initData.inFileAddr);
        int counter = 0; // 用于计算该段已经向内存中读入了多少字节
        while(counter < noffH.initData.size){
            // 接下来将向内存中写入最多一页的数据
            // virtualAddr 指明了接下来写入的第一个字节的地址，并由此来定位将写入的页 
            int virtualAddr = noffH.initData.virtualAddr + counter;
            // 定位写入的起始位置
            int virtualPage = virtualAddr / PageSize;
            int offset = virtualAddr %  PageSize ; 
            int physicalPage = pageTable[virtualPage].physicalPage;
            // 向内存中写的目标位置
            int physicalAddr = physicalPage * PageSize + offset;
            // 确定要写入的长度
            // 当前页允许写入的长度 pageLast
            int pageLast = PageSize - offset;
            // noffH.iniiData.size - counter 指明剩余的总长
            int size = ((noffH.initData.size - counter) > pageLast) ? pageLast : (noffH.initData.size - counter);
            DEBUG('a',"Writing initData segment  into Mem , at virualAddr 0x%x, size %d physicalAddr 0x%x physicalPage %d offset %d\n", 
			virtualAddr, size, physicalAddr,physicalPage, offset);
            // 在可执行文件中的位置 noffH.initData.inFileAddr + counter
            executable->ReadAt(&(machine->mainMemory[physicalAddr]),
			size, noffH.initData.inFileAddr + counter);

            // 更新counter
            counter += size;
        }        
    }

}

//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
// 	Dealloate an address space.  Nothing for now!
//----------------------------------------------------------------------

AddrSpace::~AddrSpace()
{
    DEBUG('a', "distroy the addrspace pid:%d clear frame :",pid);
    // 将用户进程的地址空间回收
    for (int i = 0; i < numPages; i++) {
	    int page = pageTable[i].physicalPage;
        if(globalPageTable[page].valid == false)
            continue;
        ASSERT(frameMap->Test((int)page));
        frameMap->Clear((int)page);
        globalPageTable[page].valid = false;
        DEBUG('a', " %d ,",page);
    }
    DEBUG('a',"\n");
    
    DEBUG('a', "semaphore pid:%d ->V()\n",pid);

    ASSERT(joinMutex[pid] != NULL);
    joinMutex[pid]->V();

    // 回收他的子进程 pid
    for(int i = 0;i < 100;i++){
        int cPid = childPid[i];
        if(cPid != -1){
            ASSERT(pidMap->Test(cPid));
            pidMap->Clear(cPid);
        }

    }
    
   delete [] pageTable;
}

//----------------------------------------------------------------------
// AddrSpace::InitRegisters
// 	Set the initial values for the user-level register set.
//
// 	We write these directly into the "machine" registers, so
//	that we can immediately jump to user code.  Note that these
//	will be saved/restored into the currentThread->userRegisters
//	when this thread is context switched out.
//----------------------------------------------------------------------

void
AddrSpace::InitRegisters()
{
    int i;

    for (i = 0; i < NumTotalRegs; i++)
	machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start"
    machine->WriteRegister(PCReg, 0);	

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    machine->WriteRegister(NextPCReg, 4);

   // Set the stack register to the end of the address space, where we
   // allocated the stack; but subtract off a bit, to make sure we don't
   // accidentally reference off the end!
    machine->WriteRegister(StackReg, numPages * PageSize - 16);
    DEBUG('a', "Initializing stack register to %d\n", numPages * PageSize - 16);
}

//----------------------------------------------------------------------
// AddrSpace::SaveState
// 	On a context switch, save any machine state, specific
//	to this address space, that needs saving.
//
//	For now, nothing!
//----------------------------------------------------------------------

void AddrSpace::SaveState() 
{}

//----------------------------------------------------------------------
// AddrSpace::RestoreState
// 	On a context switch, restore the machine state so that
//	this address space can run.
//磁盘
//      For now, tell the machine where to find the page table.
//----------------------------------------------------------------------

void AddrSpace::RestoreState() 
{
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}


//----------------------------------------------------------------------
// AddrSpace::Pirint()
// 在为一个应用程序新建一个地址空间后调用该函数，输出该程序的页表（页面与帧的
// 映射关系），显示信息有助于后续程序的调试与开发。
//----------------------------------------------------------------------

void AddrSpace::Print() 
{
    printf("page table dump: %d pages in total\n", numPages);
    printf("===============BEGIN==============\n");
    printf("\tVirtPage, \tPhysPage\n");

    for(int i=0; i < numPages; i++) {
        printf("\t %d, \t\t%d\n", pageTable[i].virtualPage, pageTable[i].physicalPage);
    }
    printf("===============END================\n\n");
}


//----------------------------------------------------------------------
// AddrSpace::getSpaceID
// 	得到本用户进程的SpaceId
//----------------------------------------------------------------------

int AddrSpace::getSpaceID() 
{
    return pid;
}



//----------------------------------------------------------------------
// AddrSpace::wait(int SpaceId)
// 	等待SpaceId执行结束
//----------------------------------------------------------------------

void AddrSpace::wait(int SpaceId)
{
    // 执行wait 操作
    DEBUG('a', "semaphore pid %d ->P()\n",SpaceId);
    printf("semaphore pid %d ->P()\n",SpaceId);
    ASSERT(joinMutex[SpaceId] != NULL);
    joinMutex[SpaceId]->P();
    delete joinMutex[SpaceId];
}

//----------------------------------------------------------------------
// AddrSpace::getFileDescriptor(OpenFile* openfile)
// 	将openfile加入打开文件表，并返回文件描述符
//----------------------------------------------------------------------

int AddrSpace::getFileDescriptor(OpenFile* openfile){
    int freeEntry  = -1;
    for(int i = 3;i < 10;i++){
        if(openFileTable[i] == nullptr){
            freeEntry = i;
            // 将打开文件指针加入
            openFileTable[i] = openfile;
            break;
        }
    }
    // 如果没有空余项，返回-1
    return freeEntry;
}

//----------------------------------------------------------------------
//  OpenFile* AddrSpace::getOpenFile(int)
// 	根据文件描述符，返回打开文件指针
//----------------------------------------------------------------------


 OpenFile* AddrSpace::getOpenFile(int fileid){
    //ASSERT(fileid > 2 && fileid < 10);
    return openFileTable[fileid];
 }

//----------------------------------------------------------------------
//  fileRedirect(int fid, OpenFile* openfile)
// 	将文件描述符 和打开文件的指针重新绑定
//----------------------------------------------------------------------


 void AddrSpace::fileRedirect(int fid, OpenFile* openfile){
     openFileTable[fid] = openfile;

 }


 //----------------------------------------------------------------------
//  freleaseFileDescriptor(int fileId)
// 	将文件描述符从表中删除
//----------------------------------------------------------------------


 void AddrSpace::releaseFileDescriptor(int fileId){
    
     openFileTable[fileId] = nullptr;
 }



 //----------------------------------------------------------------------
//  int AddrSpace::swapOut()
//  并返回被换出的页的物理页号
//----------------------------------------------------------------------



int 
AddrSpace::swapOut(){
    // 将一个页面从内存中换出

    // 采用随机算法，在物理页中，随机选择一个页
    int page = Random()%NumPhysPages;
    // 将磁盘上的SWAP 文件打开
    char  swap[5] = {'S','W','A','P','\0'};
    OpenFile* swapfile = fileSystem->Open(swap);
    // 在全局页表中，将该页置为无效
    globalPageTable[page].valid  = false;



    int size = 128;
    int physicalAddr = page * 128;

    ASSERT(swapMap->NumClear() > 0);
    // 在swap页中寻找一块
    int diskPage = swapMap->Find();

    // 记录swapTabel
    // swapTable中记录了swap文家中，现有的页的信息
    SwapTable[diskPage].virtualPage = globalPageTable[page].virtualPage;
    SwapTable[diskPage].diskPage = diskPage;  //在硬盘上SWAP区的位置  
    SwapTable[diskPage].pid =  globalPageTable[page].pid;       // 进程号
    SwapTable[diskPage].valid = true; 

    printf("SWAP: diskPage: %d \n",diskPage);
    // 将这一页写入磁盘
    swapfile->WriteAt(&(machine->mainMemory[physicalAddr]),
			size, diskPage*128);
    return page;
}


 //----------------------------------------------------------------------
//  void AddrSpace::swapIn(int vpn)
//  将对应页从swap换入页表
//----------------------------------------------------------------------
 
void AddrSpace::swapIn(int virtualPage){
    int newPage = frameMap->Find();
        if(newPage == -1){
            printf("SWAP: do swap OUT\n");
            // 内存中没有空闲的页，将一个页随即替换掉。返回患处的页号
            newPage = swapOut();

        }
	    pageTable[virtualPage].virtualPage = virtualPage;	
	    pageTable[virtualPage].physicalPage = newPage;
	    pageTable[virtualPage].valid = TRUE;
	    pageTable[virtualPage].use = FALSE;
	    pageTable[virtualPage].dirty = FALSE;
	    pageTable[virtualPage].readOnly = FALSE;  // if the code segment was entirely on 
					// a separate page, we could set its 
					// pages to be read-only

        // 填入全局页表
        globalPageTable[newPage].virtualPage = virtualPage;	
        globalPageTable[newPage].physicalPage = newPage;
        globalPageTable[newPage].valid = TRUE;
        globalPageTable[newPage].use = FALSE;
        globalPageTable[newPage].dirty = FALSE;
        globalPageTable[newPage].readOnly = FALSE; 
        globalPageTable[newPage].pid = pid;


    // 从swap区读入
    int diskPage = -1;
    for(int i =  0 ;i < NumPhysPages;i++){
        if(SwapTable[i].virtualPage == virtualPage &&
            SwapTable[i].pid == pid&&       // 进程号
            SwapTable[i].valid == true){
                diskPage = i; // 找到磁盘页
                SwapTable[i].valid == false;
                printf("swap In did:diskPage %d \n",diskPage);
                break;
        } 
    }
    swapMap->Clear(diskPage);
    int size = 128;
    char  swap[5] = {'S','W','A','P','\0'};
    OpenFile* swapfile = fileSystem->Open(swap);
    swapfile->ReadAt(&(machine->mainMemory[newPage]),
			size, diskPage*128);
    printf("swap In finish \n");
}